package com.层序遍历二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
	List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
    	 List<Integer> list = new ArrayList<Integer>();
    	 Queue<TreeNode> q = new LinkedList<TreeNode>();
         TreeNode last,nlast = null;
         //nlast是指向每一行的最后一个点，last指向当前的这个点
         last=root;
         q.offer(root);
         TreeNode temp;
         while(!q.isEmpty()) {
        	 temp=q.poll();
        	 list.add(temp.val);
        	 if(temp.left!=null) {
        		 q.offer(temp.left);
        		 nlast=temp.left;
        	 }
        	 if(temp.right!=null) {
        		 q.offer(temp.right);
        		 nlast=temp.right;
        	 }
        	 if(temp==last) {//一行结束
        		 last=nlast;
        		 result.add(list);
        		 list = new ArrayList<Integer>();
        	 }
         }
		 return result;
        
    }
    class Solution1 {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
           if(pRoot==null)return result;
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(pRoot);
            ArrayList<Integer> list = new ArrayList<Integer>();
            TreeNode temp,last,nlast;
            nlast=null;
            last = pRoot;
            while(!q.isEmpty()){
                temp=q.poll();
                list.add(temp.val);
                if(temp.left!=null){
                    q.offer(temp.left);
                    nlast=temp.left;
                }
                if(temp.right!=null){
                    q.offer(temp.right);
                    nlast=temp.right;
                }
                if(temp==last){
                    last = nlast;
                    result.add(list);
                    list = new ArrayList<Integer>();
                }
            }
            return result;
        }
        
    }
}
